package leetcode_1001_1100;

import java.util.Arrays;

public class LeeCode_1040 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(numMovesStonesII(new int[]{7, 4, 9})));
        System.out.println(Arrays.toString(numMovesStonesII(new int[]{6,5,4,3,10})));
    }
    private static int[] numMovesStonesII(int[] s) {
        int n = s.length;
        Arrays.sort(s);
        int e1 = s[n - 2] - s[0] - n + 2;
        int e2 = s[n - 1] - s[1] - n + 2;
        int maxMove = Math.max(e1, e2);
        if (e1 == 0 || e2 == 0)
            return new int[]{Math.min(2, maxMove), maxMove};
        int maxCnt = 0, left = 0;
        for (int right = 0; right < n; ++right) {
            while (s[right] - s[left] + 1 > n){
                ++left;
            }
            maxCnt = Math.max(maxCnt, right - left + 1);
        }
        return new int[]{n - maxCnt, maxMove};
    }
}
